package leetcode.median;

import leetcode.base.ListNode;

public class $328_OddEvenList {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode tail = head;
        int len = 1;
        while (tail.next != null) {
            tail = tail.next;
            len++;
        }
        ListNode p = head;
        for (int i = 1;i <= len / 2;i++) {
            ListNode even = p.next;
            ListNode odd = even.next;
            tail.next = even;
            tail = tail.next;
            tail.next = null;
            p.next = odd;
            p = p.next;
        }
        return head;
    }
    public ListNode oddEvenList2(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = head.next;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;

            even.next = odd.next;
            even = even.next;
        }


        odd.next = evenHead;
        return head;
    }
}
